unit u_astar;

interface

uses

  u_load;

var
  longueur : integer;
  largeur : integer;

type
  T_case = record
    x : integer;
    y : integer;
    g : integer;
    h : integer;
    f : integer;
    px : integer;
    py : integer;
  end;
  T_Liste = array of T_case;
  T_TabBool = array[0..3] of boolean;
  T_Move = record
    x : integer;
    y : integer;
  end;
  T_Path = array of T_Move;
  T_map_astar = array of array of integer;
  t_tabk = array of t_move;

  C_Astar = class
    private
      map_astar           : T_map_astar;
      open,closed         : T_Liste;
      diagonale           : T_TabBool;
      start,goal,now,temp : T_case;
      function plus_petit(liste : T_Liste)           : integer;
      function present(liste : T_Liste ; c : T_Case) : integer;
      procedure adjacente(map : T_map_astar);
      procedure inserer(var liste : T_Liste ; c : T_case);
      procedure supprimer_rang(var liste : T_Liste ; i : integer);
      procedure supprimer_element(var liste : T_Liste ; c : T_case);
      procedure inserer_rang(var liste : T_Path ; i : integer ; e : T_Move);
      procedure creation_map(etage,tx,ty : integer ; map : T_map_obj);
      procedure creation_map_k(etage,tx,ty : integer ; map : T_map_obj ; ka : t_tabk);
    public
      chemin : T_Liste;
      function pythagore(x,y,z,t : integer)          : integer;
      procedure astar(map : T_map_astar);
      function retourne(x,y : integer) : T_Move;
      function retourne_ck(x,y,etge : integer ;var map : t_map) : T_Move;
      procedure init_sg(depx,depy,arrx,arry,etage,tx,ty : integer ; map : T_Map_obj);
      function init_sg_k(depx,depy,arrx,arry,etage,tx,ty : integer ; map : T_Map_obj ; ka : t_tabk) : boolean;
      constructor create;

  end;

implementation

uses u_engine, u_mesh;

constructor c_astar.create;
begin
  inherited create;
  SetLength(chemin, 1);
  chemin[Low(chemin)].x := mymesh.dep_eta.x;
  chemin[Low(chemin)].y := mymesh.dep_eta.y;
end;

procedure C_Astar.inserer_rang(var liste : T_Path ; i : integer ; e : T_Move);
var
  j : integer;
begin
  setlength(liste,length(liste)+1);
  for j := high(liste) downto (i+1) do
    liste[j] := liste[j-1];
  liste[i] := e;
end;

procedure C_Astar.inserer(var liste : T_Liste ; c : T_case);
var
  l : integer;
begin
  l := length(liste);
  setlength(liste,(l+1));
  liste[l] := c;
end;

procedure C_Astar.supprimer_rang(var liste : T_Liste ; i : integer);
var
  j : integer;
begin
  if i = high(liste) then
    setlength(liste,length(liste)-1)
  else
    begin
      for j := i to high(liste)-1 do
          liste[j] := liste[j+1];
      setlength(liste,length(liste)-1);
    end;
end;

procedure C_Astar.supprimer_element(var liste : T_Liste ; c : T_case);
var
  i : integer;
begin
  i := low(liste);
  while (liste[i].x <> c.x) or (liste[i].y <> c.y) do
    i := i+1;
  supprimer_rang(liste,i);
end;

function C_Astar.pythagore;
begin
  result := trunc(sqrt((x-z)*(x-z))+((z-t)*(z-t)));
end;

function C_Astar.plus_petit;
var
  i,j : integer;
begin
  j := low(liste);
  for i := low(liste) to high(liste) do
    begin
      if liste[i].f < liste[j].f then
        j := i;
    end;
  result := j;
end;

function C_Astar.present;
var
  i,j : integer;
begin
  j := -1 ;
  if length(liste) > 0 then
    begin
      i := low(liste);
      while (i <= high(liste)) and (j = -1) do
        begin
          if (liste[i].x = c.x) and (liste[i].y = c.y) then
            j := i;
          i := i + 1;
        end;
    end;
  result := j;
end;

procedure C_Astar.adjacente(map : T_map_astar);
var
  i,k,x,y : integer;
begin
  for i := 0 to 3 do
    self.diagonale[i] := true;
  x := self.now.x;
  y := self.now.y + 1;
  if y < largeur then
    if map[x,y] <> 1 then
      begin
        self.temp.x := x;
        self.temp.y := y;
        self.temp.g := self.now.g + 10;
        self.temp.h := pythagore(x,y,self.goal.x,self.goal.y);
        self.temp.f := self.temp.g + self.temp.h;
        self.temp.px := self.now.x;
        self.temp.py := self.now.y;
        k := present(self.closed,self.temp);
        if k = -1 then
          begin
            k := self.present(self.open,self.temp);
            if (k <> -1) then
              begin
                if self.open[k].f > self.temp.f then
                  begin
                    self.open[k].g := self.temp.g;
                    self.open[k].f := self.temp.f;
                    self.open[k].px := self.temp.px;
                    self.open[k].py := self.temp.py;
                  end;
              end
            else
              self.inserer(self.open,self.temp);
          end
        else
          begin
            if self.closed[k].f > self.temp.f then
              begin
                self.supprimer_rang(self.closed,k);
                self.inserer(self.open,self.temp);
              end;
          end;
      end
    else
      self.diagonale[0] := false;
  x := self.now.x;
  y := self.now.y -1;
  if y >= 0 then
    if map[x,y] <> 1 then
      begin
        self.temp.x := x;
        self.temp.y := y;
        self.temp.g := self.now.g + 10;
        self.temp.h := pythagore(x,y,self.goal.x,self.goal.y);
        self.temp.f := self.temp.g + self.temp.h;
        self.temp.px := self.now.x;
        self.temp.py := self.now.y;
        k := self.present(self.closed,self.temp);
        if k = -1 then
          begin
            k := self.present(self.open,self.temp);
            if (k <> -1) then
              begin
                if self.open[k].f > self.temp.f then
                  begin
                    self.open[k].g := self.temp.g;
                    self.open[k].f := self.temp.f;
                    self.open[k].px := self.temp.px;
                    self.open[k].py := self.temp.py;
                  end;
              end
            else
              inserer(self.open,self.temp);
          end
        else
          begin
            if self.closed[k].f > self.temp.f then
              begin
                supprimer_rang(self.closed,k);
                inserer(self.open,self.temp);
              end;
          end;
      end
    else
      self.diagonale[1] := false;
  x := self.now.x + 1;
  y := self.now.y;
  if x < longueur then
    if map[x,y] <> 1 then
      begin
        self.temp.x := x;
        self.temp.y := y;
        self.temp.g := self.now.g + 10;
        self.temp.h := pythagore(x,y,self.goal.x,self.goal.y);
        self.temp.f := self.temp.g + self.temp.h;
        self.temp.px := self.now.x;
        self.temp.py := self.now.y;
        k := self.present(self.closed,self.temp);
        if k = -1 then
          begin
            k := self.present(self.open,self.temp);
            if (k <> -1) then
              begin
                if self.open[k].f > self.temp.f then
                  begin
                    self.open[k].g := self.temp.g;
                    self.open[k].f := self.temp.f;
                    self.open[k].px := self.temp.px;
                    self.open[k].py := self.temp.py;
                  end;
              end
            else
              inserer(self.open,self.temp);
          end
        else
          begin
            if self.closed[k].f > self.temp.f then
              begin
                supprimer_rang(self.closed,k);
                inserer(self.open,self.temp);
              end;
          end;
      end
    else
      self.diagonale[2] := false;
  x := self.now.x - 1;
  y := self.now.y;
  if x >= 0 then
    if map[x,y] <> 1 then
      begin
        self.temp.x := x;
        self.temp.y := y;
        self.temp.g := self.now.g + 10;
        self.temp.h := pythagore(x,y,self.goal.x,self.goal.y);
        self.temp.f := self.temp.g + self.temp.h;
        self.temp.px := self.now.x;
        self.temp.py := self.now.y;
        k := self.present(self.open,self.temp);
        k := self.present(self.closed,self.temp);
        if k = -1 then
          begin
            k := self.present(self.open,self.temp);
            if (k <> -1) then
              begin
                if self.open[k].f > self.temp.f then
                  begin
                    self.open[k].g := self.temp.g;
                    self.open[k].f := self.temp.f;
                    self.open[k].px := self.temp.px;
                    self.open[k].py := self.temp.py;
                  end;
              end
            else
              inserer(self.open,self.temp);
          end
        else
          begin
            if self.closed[k].f > self.temp.f then
              begin
                supprimer_rang(self.closed,k);
                inserer(self.open,self.temp);
              end;
          end;
      end
    else
      self.diagonale[3] := false;
  x := self.now.x + 1;
  y := self.now.y - 1;
  if (x < longueur) and (y >= 0) then
    if (self.diagonale[1] or self.diagonale[2]) and (map[x,y] <> 1) then
      begin
        self.temp.x := x;
        self.temp.y := y;
        self.temp.g := self.now.g + 14;
        self.temp.h := pythagore(x,y,self.goal.x,self.goal.y);
        self.temp.f := self.temp.g + self.temp.h;
        self.temp.px := self.now.x;
        self.temp.py := self.now.y;
        k := self.present(self.closed,self.temp);
        if k = -1 then
          begin
            k := self.present(self.open,self.temp);
            if (k <> -1) then
              begin
                if self.open[k].f > self.temp.f then
                  begin
                    self.open[k].g := self.temp.g;
                    self.open[k].f := self.temp.f;
                    self.open[k].px := self.temp.px;
                    self.open[k].py := self.temp.py;
                  end;
              end
            else
              inserer(self.open,self.temp);
          end
        else
          begin
            if self.closed[k].f > self.temp.f then
              begin
                supprimer_rang(self.closed,k);
                inserer(self.open,self.temp);
              end;
          end;
      end;
  x := self.now.x + 1;
  y := self.now.y + 1;
  if (x < longueur) and (y < largeur) then
    if (self.diagonale[0] or self.diagonale[2]) and (map[x,y] <> 1) then
      begin
        self.temp.x := x;
        self.temp.y := y;
        self.temp.g := self.now.g + 14;
        self.temp.h := pythagore(x,y,self.goal.x,self.goal.y);
        self.temp.f := self.temp.g + self.temp.h;
        self.temp.px := self.now.x;
        self.temp.py := self.now.y;
        k := self.present(self.closed,self.temp);
        if k = -1 then
          begin
            k := self.present(self.open,self.temp);
            if (k <> -1) then
              begin
                if self.open[k].f > self.temp.f then
                  begin
                    self.open[k].g := self.temp.g;
                    self.open[k].f := self.temp.f;
                    self.open[k].px := self.temp.px;
                    self.open[k].py := self.temp.py;
                  end;
              end
            else
              inserer(self.open,self.temp);
          end
        else
          begin
            if self.closed[k].f > self.temp.f then
              begin
                supprimer_rang(self.closed,k);
                inserer(self.open,self.temp);
              end;
          end;
      end;
  x := self.now.x - 1;
  y := self.now.y - 1;
  if (x >= 0) and (y >= 0) then
    if (self.diagonale[1] or self.diagonale[3]) and (map[x,y] <> 1) then
      begin
        self.temp.x := x;
        self.temp.y := y;
        self.temp.g := self.now.g + 14;
        self.temp.h := pythagore(x,y,self.goal.x,self.goal.y);
        self.temp.f := self.temp.g + self.temp.h;
        self.temp.px := self.now.x;
        self.temp.py := self.now.y;
        k := self.present(self.closed,self.temp);
        if k = -1 then
          begin
            k := self.present(self.open,self.temp);
            if (k <> -1) then
              begin
                if self.open[k].f > self.temp.f then
                  begin
                    self.open[k].g := self.temp.g;
                    self.open[k].f := self.temp.f;
                    self.open[k].px := self.temp.px;
                    self.open[k].py := self.temp.py;
                  end;
              end
            else
              inserer(self.open,self.temp);
          end
        else
          begin
            if self.closed[k].f > self.temp.f then
              begin
                supprimer_rang(self.closed,k);
                inserer(self.open,self.temp);
              end;
          end;
      end;
  x := self.now.x - 1;
  y := self.now.y + 1;
  if (x >= longueur) and (y < largeur) then
    if (self.diagonale[0] or self.diagonale[3]) and (map[x,y] <> 1) then
      begin
        self.temp.x := x;
        self.temp.y := y;
        self.temp.g := self.now.g + 14;
        self.temp.h := pythagore(x,y,self.goal.x,self.goal.y);
        self.temp.f := self.temp.g + self.temp.h;
        self.temp.px := self.now.x;
        self.temp.py := self.now.y;
        k := self.present(self.closed,self.temp);
        if k = -1 then
          begin
            k := self.present(self.open,self.temp);
            if (k <> -1) then
              begin
                if self.open[k].f > self.temp.f then
                  begin
                    self.open[k].g := self.temp.g;
                    self.open[k].f := self.temp.f;
                    self.open[k].px := self.temp.px;
                    self.open[k].py := self.temp.py;
                  end;
              end
            else
              inserer(self.open,self.temp);
          end;
      end;
end;

procedure C_Astar.astar(map : T_map_astar);
var
  i,l : integer;
  vide : boolean;
begin
  l := 1;
  setlength(self.open,1);
  setlength(self.closed,0);
  setlength(self.chemin,0);
  if map[self.goal.x,self.goal.y] = 1 then
    begin
      vide := false;
      map[self.goal.x,self.goal.y] := 0;
    end
  else
    vide := true;
  self.open[0] := self.start;
  self.now.x := self.start.x;
  self.now.y := self.start.y;
  while (l <> 0) do
    begin
      i := self.plus_petit(self.open);
      self.now := self.open[i];
      if ((self.now.x = self.goal.x) and (self.now.y = self.goal.y)) then
        l := 0
      else
        begin
          self.supprimer_rang(self.open,i);
          self.adjacente(map);
          self.inserer(self.closed,self.now);
          l := length(self.open);
        end;
    end;
  if ((self.now.x = self.goal.x) and (self.now.y = self.goal.y)) then
    begin
      if vide then
        self.inserer(self.chemin,self.now)
      else
        map[self.now.x,self.now.y] := 1;
      while (self.now.x <> self.start.x) or (self.now.y <> self.start.y) do
        begin
          self.temp.x := self.now.px;
          self.temp.y := self.now.py;
          i := self.present(closed,temp);
          self.now := self.closed[i];
          self.supprimer_rang(closed,i);
          self.inserer(chemin,now);
        end;
    end;
  if length(self.chemin) > 0 then
    setlength(self.chemin,length(self.chemin)-1);
  //else
    //self.inserer(chemin,start);
end;

function C_astar.retourne_ck(x,y,etge : integer ;var map : t_map) : T_Move;
begin
  if length(self.chemin) = 0 then
    begin
      result.x := x;
      result.y := y;
    end
  else
    begin
      if (map[etge,self.chemin[high(self.chemin)].x,self.chemin[high(self.chemin)].y]._type <> 'none')then
        begin
          result.x := x;
          result.y := y;
        end
      else
        begin
          result.x := self.chemin[high(self.chemin)].x;
          result.y := self.chemin[high(self.chemin)].y;
          setlength(self.chemin,length(self.chemin)-1);
        end;
//  if high(self.chemin) > low(self.chemin) then
    end;
end;

function C_astar.retourne(x,y : integer) : T_Move;
begin
  if length(self.chemin) = 0 then
    begin
      result.x := x;
      result.y := y;
    end
  else
    begin
      result.x := self.chemin[high(self.chemin)].x;
      result.y := self.chemin[high(self.chemin)].y;
      setlength(self.chemin,length(self.chemin)-1);
    end;
//  if high(self.chemin) > low(self.chemin) then
end;

procedure C_astar.creation_map(etage,tx,ty : integer ; map : T_map_obj);
var
  i,j : integer;
begin
  setlength(self.map_astar,tx);
  for i := low(self.map_astar) to high(self.map_astar) do
    setlength(self.map_astar[i],ty);
  for i := low(self.map_astar) to high(Self.map_astar) do
    for j := low(self.map_astar[i]) to high(self.map_astar[i]) do
      begin
        map_astar[i,j] := 0;
      end;
  for i := 0 to high(map[etage]) do
    begin
      if map[etage][i].objet._type <> 'none' then
        begin
          for j := 0 to high(map[etage][i].tab_etage) do
            map_astar[map[etage][i].tab_etage[j].x,map[etage][i].tab_etage[j].y] := 1;
        end;
    end;
end;

procedure C_astar.creation_map_k(etage,tx,ty : integer ; map : T_map_obj ; ka : t_tabk);
var
  i,j : integer;
begin
  setlength(self.map_astar,tx);
  for i := low(self.map_astar) to high(self.map_astar) do
    setlength(self.map_astar[i],ty);
  for i := low(self.map_astar) to high(Self.map_astar) do
    for j := low(self.map_astar[i]) to high(self.map_astar[i]) do
      begin
        map_astar[i,j] := 0;
      end;
  for i := 0 to high(map[etage]) do
    begin
      if map[etage][i].objet._type <> 'none' then
        begin
          for j := 0 to high(map[etage][i].tab_etage) do
            map_astar[map[etage][i].tab_etage[j].x,map[etage][i].tab_etage[j].y] := 1;
        end;
    end;
  for i := 0 to high(ka) do
    map_astar[ka[i].x,ka[i].y] := 1;
end;

procedure C_astar.init_sg(depx,depy,arrx,arry,etage,tx,ty : integer ; map : T_map_obj);
begin
  largeur := ty;
  longueur := tx;
  self.start.x := depx;
  self.start.y := depy;
  self.goal.x := arrx;
  self.goal.y := arry;
  self.creation_map(etage,tx,ty,map);
  self.astar(self.map_astar);
end;

function C_astar.init_sg_k(depx,depy,arrx,arry,etage,tx,ty : integer ; map : T_Map_obj ; ka : t_tabk) : boolean;
begin
  largeur := ty;
  longueur := tx;
  result := false;
  self.start.x := depx;
  self.start.y := depy;
  self.goal.x := arrx;
  self.goal.y := arry;
  self.creation_map_k(etage,tx,ty,map,ka);
  self.astar(self.map_astar);
  if length(self.chemin) > 0 then
    result := true;
end;

{procedure C_Astar.init_test();
var
  i,j : integer;
begin
  for i := 0 to 49 do
    for j := 0 to 49 do
      map[j,i] := 0;
  for i := 10 to 30 do
    begin
      map[10,i] := 1;
      map[30,i] := 1;
      map[i,10] := 1;
      map[i,30] := 1;
    end;
  self.start.x := 2;
  self.start.y := 2;
  self.goal.x := 35;
  self.goal.y := 40;
  map[35,40] := 1;
end;

procedure C_Astar.affichage();
var
  i,j : integer;
begin
  for i := 0 to 49 do
    begin
      for j := 0 to 49 do
        write(map[j,i]);
      writeln;
    end;
  for i := high(self.chemin) downto low(self.chemin) do
    map[self.chemin[i].x,self.chemin[i].y] := 4;
  writeln;
  for i := 0 to 49 do
    begin
      for j := 0 to 49 do
        write(map[j,i]);
      writeln;
    end;
end;}

end.
